/**
 * 快速排序算法
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(logn)
 */
public class QuickSortAlgorithm {
    /**
     * 快速排序实现（非降序排序）
     * 左闭右闭区间
     * @param array： 待排序数组
     * @param left： 左边界
     * @param right： 右边界
     */
    public static void quickSort(int[] array, int left, int right){
        if(right <= left){
            return;
        }
        int pivot = left + (right - left) / 2;
        // 先将轴值移动到数组末尾
        int temp = array[right];
        array[right] = array[left];
        array[left] = temp;
        // 切割数组
        pivot = partition(array, left, right);
        quickSort(array, left, pivot - 1);
        quickSort(array, pivot + 1, right);
    }

    /**
     * 切割数组，将小往左放，大的往右放
     * @param array： 待切割数组
     * @param _left： 左边界
     * @param _right： 右边界
     * @return 切割点
     */
    private static int partition(int[] array, int _left, int _right){
        int left = _left;
        int right = _right;
        int temp = array[right];
        while(left < right){
            while(array[left] <= temp && left < right){
                left++;
            }
            if(left < right){
                array[right] = array[left];
                right--;
            }
            while(array[right] >= temp && left < right){
                right--;
            }
            if(left < right){
                array[left] = array[right];
                left++;
            }
        }
        array[left] = temp;
        return left;
    }

    public static void main(String[] args) {
        int[] array = new int[]{6, 5, 4, 3, 2, 1};
        for (int value: array) {
            System.out.print(value + " ");
        }
        System.out.println();
        QuickSortAlgorithm.quickSort(array, 0, array.length - 1);
        for (int value: array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
